#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2019/11/25 08:59|08:59
# @Author  : yangdingyi
# @File    : 长度最小的子数组
# @Software: PyCharm
from typing import List


class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        # n = len(nums)
        # i, j = 0, 0
        # ans = 0
        # m = 0
        # while j < n:  # 可以用for枚举
        #     if m < s:  # 是否一定要判断
        #         m += nums[j]
        #         j += 1
        #     if m >= s:
        #         if ans == 0 or j-i < ans:
        #             ans = j-i
        #         while m >= s:
        #             m -= nums[i]
        #             i += 1
        #             if m >= s and (ans == 0 or j-i < ans):
        #                 ans = j-i
        # return ans
        # 1. 双指针,简化 O(n)
        # ans, m, j = 0, 0, 0
        # for i, a in enumerate(nums):
        #     m += a
        #     while m >= s:
        #         if ans == 0 or i - j + 1 < ans:
        #             ans = i - j + 1
        #         m -= nums[j]
        #         j += 1
        # return ans
        # 2. 二分查找 O(nlogn)
        n = len(nums)
        sum = [0]
        m = 0
        ans = 0
        for i, a in enumerate(nums):
            m += a
            sum.append(m)

        def search(arr: List[int], ll: int, rr: int, t: int):
            while ll < rr:
                h = (ll + rr) // 2
                x = arr[h]
                if t == x:  # 正整数，所以都不相等
                    return h
                elif t < x:
                    rr = h
                else:
                    ll = h + 1
            return ll if arr[ll] >= t else -1

        for i, a in enumerate(nums):
            ti = search(sum, i, n, s+sum[i])
            if ti >= 0 and (ans == 0 or ti-i < ans):
                ans = ti-i
        return ans


solve = Solution()
s = 7
nums = [2, 3, 1, 2, 4, 3]
# s = 4
# nums = [1, 4, 4]
print(nums, s)
print(solve.minSubArrayLen(s, nums))
